/*
 * @Author: w
 * @Date: 2022年02月15日16:17:58
 * @Description: 3. 无重复字符的最长子串
 */

// 我的
var lengthOfLongestSubstring = function (s) {
  // 空字符串返回0
  if (s.length == 0) return 0;
  // 不需要split 直接遍历字符串
  const arr = s.split("");
  let record = [arr[0]];
  let length = 1;
  for (let index = 1; index < arr.length; index++) {
    // 不需要创建新变量
    let item = arr[index];
    let rindex = record.indexOf(item);
    if (rindex != -1) {
      length = Math.max(length, record.length);
      record = record.slice(rindex + 1);
      record.push(item);
    }
    // 不需要写else
    else {
      record.push(item);
    }
  }
  // 最后一个字符串比较
  length = Math.max(length, record.length);
  return length;
};

// 官方 滑动窗口
// 使用hash 窗口（双指针）
var lengthOfLongestSubstring = function (s) {
  // 哈希集合，记录每个字符是否出现过
  const occ = new Set();
  const n = s.length;
  // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
  let rk = -1,
    ans = 0;
  for (let i = 0; i < n; ++i) {
    // 移动左指针 直到没有重复
    if (i != 0) {
      // 左指针向右移动一格，移除一个字符
      occ.delete(s.charAt(i - 1));
    }
    // 无穷找到重复的
    while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
      // 不断地移动右指针
      occ.add(s.charAt(rk + 1));
      ++rk;
    }
    // 第 i 到 rk 个字符是一个极长的无重复字符子串
    ans = Math.max(ans, rk - i + 1);
  }
  return ans;
};

// 最快
var lengthOfLongestSubstring = function (s) {
  const array = [];
  let maxLength = 0;
  [...s].forEach(char => {
    let index = array.indexOf(char);
    if (index > -1) {
      array.splice(0, index + 1);
    }
    array.push(char);
    maxLength = array.length > maxLength ? array.length : maxLength;
  });
  return maxLength;
};

// 内存
var lengthOfLongestSubstring = function (s) {
  let minIndex = 0;
  let ans = 0;
  for (let i = 0; i < s.length; i++) {
    if (s.indexOf(s[i], minIndex) < i) {
      minIndex = s.indexOf(s[i], minIndex) + 1;
    } else {
      ans = Math.max(ans, i - minIndex + 1);
    }
  }
  return ans;
};
